package code;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class TreeSide {
	static public class TreeNode {
	     int val;
	     TreeNode left;
	     TreeNode right;
		 TreeNode(int x) { val = x; }
    }
	
    public List<Integer> rightSideView(TreeNode root) {
    	
    	List<Integer> result=new ArrayList<Integer>();
    	Map<TreeNode,Integer> level=new HashMap<TreeNode,Integer>();
    	Queue<TreeNode> queue=new LinkedList<TreeNode>();
    	if(root==null)	return result;
    	queue.add(root);
    	level.put(root, 1);
    	result.add(root.val);
    	while(!queue.isEmpty()){
    		TreeNode head=queue.poll();
    		int step=level.get(head);
    		if(result.size()<step){
    			result.add(head.val);
    			System.out.println(head.val);
    		}
    		if(head.right!=null){
    			queue.add(head.right);
    			level.put(head.right, step+1);
    		}
    		if(head.left!=null){
    			queue.add(head.left);
    			level.put(head.left,step+1);
    		}
    	}
		return result;
    }
    
    public static void main(String[] args){
    	TreeNode root=new TreeNode(1);
    	TreeNode a=new TreeNode(2);
    	TreeNode b=new TreeNode(3);
    	TreeNode c=new TreeNode(4);
    	root.left=a;
    	root.right=b;
    	a.left=c;
    	new TreeSide().rightSideView(root);
    }
}
